(0) Obligation:

Runtime Complexity TRS:
The TRS R consists of the following rules:

a__aa__c
a__ba__c
a__ce
a__kl
a__dm
a__aa__d
a__ba__d
a__cl
a__km
a__Aa__h(a__f(a__a), a__f(a__b))
a__h(X, X) → a__g(mark(X), mark(X), a__f(a__k))
a__g(d, X, X) → a__A
a__f(X) → a__z(mark(X), X)
a__z(e, X) → mark(X)
mark(A) → a__A
mark(a) → a__a
mark(b) → a__b
mark(c) → a__c
mark(d) → a__d
mark(k) → a__k
mark(z(X1, X2)) → a__z(mark(X1), X2)
mark(f(X)) → a__f(mark(X))
mark(h(X1, X2)) → a__h(mark(X1), mark(X2))
mark(g(X1, X2, X3)) → a__g(mark(X1), mark(X2), mark(X3))
mark(e) → e
mark(l) → l
mark(m) → m
a__AA
a__aa
a__bb
a__cc
a__dd
a__kk
a__z(X1, X2) → z(X1, X2)
a__f(X) → f(X)
a__h(X1, X2) → h(X1, X2)
a__g(X1, X2, X3) → g(X1, X2, X3)

Rewrite Strategy: FULL

(1) DecreasingLoopProof (EQUIVALENT transformation)

The following loop(s) give(s) rise to the lower bound Ω(2n):
The rewrite sequence
mark(z(f(X35587_0), X2)) →+ a__z(a__z(mark(mark(X35587_0)), mark(X35587_0)), X2)
gives rise to a decreasing loop by considering the right hand sides subterm at position [0,0,0].
The pumping substitution is [X35587_0 / z(f(X35587_0), X2)].
The result substitution is [ ].

The rewrite sequence
mark(z(f(X35587_0), X2)) →+ a__z(a__z(mark(mark(X35587_0)), mark(X35587_0)), X2)
gives rise to a decreasing loop by considering the right hand sides subterm at position [0,1].
The pumping substitution is [X35587_0 / z(f(X35587_0), X2)].
The result substitution is [ ].

(2) BOUNDS(2^n, INF)

(3) RenamingProof (EQUIVALENT transformation)

Renamed function symbols to avoid clashes with predefined symbol.

(4) Obligation:

Runtime Complexity Relative TRS:
The TRS R consists of the following rules:

a__aa__c
a__ba__c
a__ce
a__kl
a__dm
a__aa__d
a__ba__d
a__cl
a__km
a__Aa__h(a__f(a__a), a__f(a__b))
a__h(X, X) → a__g(mark(X), mark(X), a__f(a__k))
a__g(d, X, X) → a__A
a__f(X) → a__z(mark(X), X)
a__z(e, X) → mark(X)
mark(A) → a__A
mark(a) → a__a
mark(b) → a__b
mark(c) → a__c
mark(d) → a__d
mark(k) → a__k
mark(z(X1, X2)) → a__z(mark(X1), X2)
mark(f(X)) → a__f(mark(X))
mark(h(X1, X2)) → a__h(mark(X1), mark(X2))
mark(g(X1, X2, X3)) → a__g(mark(X1), mark(X2), mark(X3))
mark(e) → e
mark(l) → l
mark(m) → m
a__AA
a__aa
a__bb
a__cc
a__dd
a__kk
a__z(X1, X2) → z(X1, X2)
a__f(X) → f(X)
a__h(X1, X2) → h(X1, X2)
a__g(X1, X2, X3) → g(X1, X2, X3)

S is empty.
Rewrite Strategy: FULL

(5) TypeInferenceProof (BOTH BOUNDS(ID, ID) transformation)

Infered types.

(6) Obligation:

TRS:
Rules:
a__aa__c
a__ba__c
a__ce
a__kl
a__dm
a__aa__d
a__ba__d
a__cl
a__km
a__Aa__h(a__f(a__a), a__f(a__b))
a__h(X, X) → a__g(mark(X), mark(X), a__f(a__k))
a__g(d, X, X) → a__A
a__f(X) → a__z(mark(X), X)
a__z(e, X) → mark(X)
mark(A) → a__A
mark(a) → a__a
mark(b) → a__b
mark(c) → a__c
mark(d) → a__d
mark(k) → a__k
mark(z(X1, X2)) → a__z(mark(X1), X2)
mark(f(X)) → a__f(mark(X))
mark(h(X1, X2)) → a__h(mark(X1), mark(X2))
mark(g(X1, X2, X3)) → a__g(mark(X1), mark(X2), mark(X3))
mark(e) → e
mark(l) → l
mark(m) → m
a__AA
a__aa
a__bb
a__cc
a__dd
a__kk
a__z(X1, X2) → z(X1, X2)
a__f(X) → f(X)
a__h(X1, X2) → h(X1, X2)
a__g(X1, X2, X3) → g(X1, X2, X3)

Types:
a__a :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__c :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__b :: e:l:m:d:A:a:b:c:k:z:f:h:g
e :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__k :: e:l:m:d:A:a:b:c:k:z:f:h:g
l :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__d :: e:l:m:d:A:a:b:c:k:z:f:h:g
m :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
mark :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
d :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a :: e:l:m:d:A:a:b:c:k:z:f:h:g
b :: e:l:m:d:A:a:b:c:k:z:f:h:g
c :: e:l:m:d:A:a:b:c:k:z:f:h:g
k :: e:l:m:d:A:a:b:c:k:z:f:h:g
z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
hole_e:l:m:d:A:a:b:c:k:z:f:h:g1_0 :: e:l:m:d:A:a:b:c:k:z:f:h:g
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0 :: Nat → e:l:m:d:A:a:b:c:k:z:f:h:g

(7) OrderProof (LOWER BOUND(ID) transformation)

Heuristically decided to analyse the following defined symbols:
a__A, a__h, a__f, a__g, mark, a__z

They will be analysed ascendingly in the following order:
a__A = a__h
a__A = a__f
a__A = a__g
a__A = mark
a__A = a__z
a__h = a__f
a__h = a__g
a__h = mark
a__h = a__z
a__f = a__g
a__f = mark
a__f = a__z
a__g = mark
a__g = a__z
mark = a__z

(8) Obligation:

TRS:
Rules:
a__aa__c
a__ba__c
a__ce
a__kl
a__dm
a__aa__d
a__ba__d
a__cl
a__km
a__Aa__h(a__f(a__a), a__f(a__b))
a__h(X, X) → a__g(mark(X), mark(X), a__f(a__k))
a__g(d, X, X) → a__A
a__f(X) → a__z(mark(X), X)
a__z(e, X) → mark(X)
mark(A) → a__A
mark(a) → a__a
mark(b) → a__b
mark(c) → a__c
mark(d) → a__d
mark(k) → a__k
mark(z(X1, X2)) → a__z(mark(X1), X2)
mark(f(X)) → a__f(mark(X))
mark(h(X1, X2)) → a__h(mark(X1), mark(X2))
mark(g(X1, X2, X3)) → a__g(mark(X1), mark(X2), mark(X3))
mark(e) → e
mark(l) → l
mark(m) → m
a__AA
a__aa
a__bb
a__cc
a__dd
a__kk
a__z(X1, X2) → z(X1, X2)
a__f(X) → f(X)
a__h(X1, X2) → h(X1, X2)
a__g(X1, X2, X3) → g(X1, X2, X3)

Types:
a__a :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__c :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__b :: e:l:m:d:A:a:b:c:k:z:f:h:g
e :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__k :: e:l:m:d:A:a:b:c:k:z:f:h:g
l :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__d :: e:l:m:d:A:a:b:c:k:z:f:h:g
m :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
mark :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
d :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a :: e:l:m:d:A:a:b:c:k:z:f:h:g
b :: e:l:m:d:A:a:b:c:k:z:f:h:g
c :: e:l:m:d:A:a:b:c:k:z:f:h:g
k :: e:l:m:d:A:a:b:c:k:z:f:h:g
z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
hole_e:l:m:d:A:a:b:c:k:z:f:h:g1_0 :: e:l:m:d:A:a:b:c:k:z:f:h:g
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0 :: Nat → e:l:m:d:A:a:b:c:k:z:f:h:g

Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)

The following defined symbols remain to be analysed:
a__h, a__A, a__f, a__g, mark, a__z

They will be analysed ascendingly in the following order:
a__A = a__h
a__A = a__f
a__A = a__g
a__A = mark
a__A = a__z
a__h = a__f
a__h = a__g
a__h = mark
a__h = a__z
a__f = a__g
a__f = mark
a__f = a__z
a__g = mark
a__g = a__z
mark = a__z

(9) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

Could not prove a rewrite lemma for the defined symbol a__h.

(10) Obligation:

TRS:
Rules:
a__aa__c
a__ba__c
a__ce
a__kl
a__dm
a__aa__d
a__ba__d
a__cl
a__km
a__Aa__h(a__f(a__a), a__f(a__b))
a__h(X, X) → a__g(mark(X), mark(X), a__f(a__k))
a__g(d, X, X) → a__A
a__f(X) → a__z(mark(X), X)
a__z(e, X) → mark(X)
mark(A) → a__A
mark(a) → a__a
mark(b) → a__b
mark(c) → a__c
mark(d) → a__d
mark(k) → a__k
mark(z(X1, X2)) → a__z(mark(X1), X2)
mark(f(X)) → a__f(mark(X))
mark(h(X1, X2)) → a__h(mark(X1), mark(X2))
mark(g(X1, X2, X3)) → a__g(mark(X1), mark(X2), mark(X3))
mark(e) → e
mark(l) → l
mark(m) → m
a__AA
a__aa
a__bb
a__cc
a__dd
a__kk
a__z(X1, X2) → z(X1, X2)
a__f(X) → f(X)
a__h(X1, X2) → h(X1, X2)
a__g(X1, X2, X3) → g(X1, X2, X3)

Types:
a__a :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__c :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__b :: e:l:m:d:A:a:b:c:k:z:f:h:g
e :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__k :: e:l:m:d:A:a:b:c:k:z:f:h:g
l :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__d :: e:l:m:d:A:a:b:c:k:z:f:h:g
m :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
mark :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
d :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a :: e:l:m:d:A:a:b:c:k:z:f:h:g
b :: e:l:m:d:A:a:b:c:k:z:f:h:g
c :: e:l:m:d:A:a:b:c:k:z:f:h:g
k :: e:l:m:d:A:a:b:c:k:z:f:h:g
z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
hole_e:l:m:d:A:a:b:c:k:z:f:h:g1_0 :: e:l:m:d:A:a:b:c:k:z:f:h:g
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0 :: Nat → e:l:m:d:A:a:b:c:k:z:f:h:g

Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)

The following defined symbols remain to be analysed:
a__g, a__A, a__f, mark, a__z

They will be analysed ascendingly in the following order:
a__A = a__h
a__A = a__f
a__A = a__g
a__A = mark
a__A = a__z
a__h = a__f
a__h = a__g
a__h = mark
a__h = a__z
a__f = a__g
a__f = mark
a__f = a__z
a__g = mark
a__g = a__z
mark = a__z

(11) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

Could not prove a rewrite lemma for the defined symbol a__g.

(12) Obligation:

TRS:
Rules:
a__aa__c
a__ba__c
a__ce
a__kl
a__dm
a__aa__d
a__ba__d
a__cl
a__km
a__Aa__h(a__f(a__a), a__f(a__b))
a__h(X, X) → a__g(mark(X), mark(X), a__f(a__k))
a__g(d, X, X) → a__A
a__f(X) → a__z(mark(X), X)
a__z(e, X) → mark(X)
mark(A) → a__A
mark(a) → a__a
mark(b) → a__b
mark(c) → a__c
mark(d) → a__d
mark(k) → a__k
mark(z(X1, X2)) → a__z(mark(X1), X2)
mark(f(X)) → a__f(mark(X))
mark(h(X1, X2)) → a__h(mark(X1), mark(X2))
mark(g(X1, X2, X3)) → a__g(mark(X1), mark(X2), mark(X3))
mark(e) → e
mark(l) → l
mark(m) → m
a__AA
a__aa
a__bb
a__cc
a__dd
a__kk
a__z(X1, X2) → z(X1, X2)
a__f(X) → f(X)
a__h(X1, X2) → h(X1, X2)
a__g(X1, X2, X3) → g(X1, X2, X3)

Types:
a__a :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__c :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__b :: e:l:m:d:A:a:b:c:k:z:f:h:g
e :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__k :: e:l:m:d:A:a:b:c:k:z:f:h:g
l :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__d :: e:l:m:d:A:a:b:c:k:z:f:h:g
m :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
mark :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
d :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a :: e:l:m:d:A:a:b:c:k:z:f:h:g
b :: e:l:m:d:A:a:b:c:k:z:f:h:g
c :: e:l:m:d:A:a:b:c:k:z:f:h:g
k :: e:l:m:d:A:a:b:c:k:z:f:h:g
z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
hole_e:l:m:d:A:a:b:c:k:z:f:h:g1_0 :: e:l:m:d:A:a:b:c:k:z:f:h:g
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0 :: Nat → e:l:m:d:A:a:b:c:k:z:f:h:g

Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)

The following defined symbols remain to be analysed:
a__A, a__f, mark, a__z

They will be analysed ascendingly in the following order:
a__A = a__h
a__A = a__f
a__A = a__g
a__A = mark
a__A = a__z
a__h = a__f
a__h = a__g
a__h = mark
a__h = a__z
a__f = a__g
a__f = mark
a__f = a__z
a__g = mark
a__g = a__z
mark = a__z

(13) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

Could not prove a rewrite lemma for the defined symbol a__A.

(14) Obligation:

TRS:
Rules:
a__aa__c
a__ba__c
a__ce
a__kl
a__dm
a__aa__d
a__ba__d
a__cl
a__km
a__Aa__h(a__f(a__a), a__f(a__b))
a__h(X, X) → a__g(mark(X), mark(X), a__f(a__k))
a__g(d, X, X) → a__A
a__f(X) → a__z(mark(X), X)
a__z(e, X) → mark(X)
mark(A) → a__A
mark(a) → a__a
mark(b) → a__b
mark(c) → a__c
mark(d) → a__d
mark(k) → a__k
mark(z(X1, X2)) → a__z(mark(X1), X2)
mark(f(X)) → a__f(mark(X))
mark(h(X1, X2)) → a__h(mark(X1), mark(X2))
mark(g(X1, X2, X3)) → a__g(mark(X1), mark(X2), mark(X3))
mark(e) → e
mark(l) → l
mark(m) → m
a__AA
a__aa
a__bb
a__cc
a__dd
a__kk
a__z(X1, X2) → z(X1, X2)
a__f(X) → f(X)
a__h(X1, X2) → h(X1, X2)
a__g(X1, X2, X3) → g(X1, X2, X3)

Types:
a__a :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__c :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__b :: e:l:m:d:A:a:b:c:k:z:f:h:g
e :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__k :: e:l:m:d:A:a:b:c:k:z:f:h:g
l :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__d :: e:l:m:d:A:a:b:c:k:z:f:h:g
m :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
mark :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
d :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a :: e:l:m:d:A:a:b:c:k:z:f:h:g
b :: e:l:m:d:A:a:b:c:k:z:f:h:g
c :: e:l:m:d:A:a:b:c:k:z:f:h:g
k :: e:l:m:d:A:a:b:c:k:z:f:h:g
z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
hole_e:l:m:d:A:a:b:c:k:z:f:h:g1_0 :: e:l:m:d:A:a:b:c:k:z:f:h:g
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0 :: Nat → e:l:m:d:A:a:b:c:k:z:f:h:g

Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)

The following defined symbols remain to be analysed:
a__f, mark, a__z

They will be analysed ascendingly in the following order:
a__A = a__h
a__A = a__f
a__A = a__g
a__A = mark
a__A = a__z
a__h = a__f
a__h = a__g
a__h = mark
a__h = a__z
a__f = a__g
a__f = mark
a__f = a__z
a__g = mark
a__g = a__z
mark = a__z

(15) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

Could not prove a rewrite lemma for the defined symbol a__f.

(16) Obligation:

TRS:
Rules:
a__aa__c
a__ba__c
a__ce
a__kl
a__dm
a__aa__d
a__ba__d
a__cl
a__km
a__Aa__h(a__f(a__a), a__f(a__b))
a__h(X, X) → a__g(mark(X), mark(X), a__f(a__k))
a__g(d, X, X) → a__A
a__f(X) → a__z(mark(X), X)
a__z(e, X) → mark(X)
mark(A) → a__A
mark(a) → a__a
mark(b) → a__b
mark(c) → a__c
mark(d) → a__d
mark(k) → a__k
mark(z(X1, X2)) → a__z(mark(X1), X2)
mark(f(X)) → a__f(mark(X))
mark(h(X1, X2)) → a__h(mark(X1), mark(X2))
mark(g(X1, X2, X3)) → a__g(mark(X1), mark(X2), mark(X3))
mark(e) → e
mark(l) → l
mark(m) → m
a__AA
a__aa
a__bb
a__cc
a__dd
a__kk
a__z(X1, X2) → z(X1, X2)
a__f(X) → f(X)
a__h(X1, X2) → h(X1, X2)
a__g(X1, X2, X3) → g(X1, X2, X3)

Types:
a__a :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__c :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__b :: e:l:m:d:A:a:b:c:k:z:f:h:g
e :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__k :: e:l:m:d:A:a:b:c:k:z:f:h:g
l :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__d :: e:l:m:d:A:a:b:c:k:z:f:h:g
m :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
mark :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
d :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a :: e:l:m:d:A:a:b:c:k:z:f:h:g
b :: e:l:m:d:A:a:b:c:k:z:f:h:g
c :: e:l:m:d:A:a:b:c:k:z:f:h:g
k :: e:l:m:d:A:a:b:c:k:z:f:h:g
z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
hole_e:l:m:d:A:a:b:c:k:z:f:h:g1_0 :: e:l:m:d:A:a:b:c:k:z:f:h:g
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0 :: Nat → e:l:m:d:A:a:b:c:k:z:f:h:g

Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)

The following defined symbols remain to be analysed:
a__z, mark

They will be analysed ascendingly in the following order:
a__A = a__h
a__A = a__f
a__A = a__g
a__A = mark
a__A = a__z
a__h = a__f
a__h = a__g
a__h = mark
a__h = a__z
a__f = a__g
a__f = mark
a__f = a__z
a__g = mark
a__g = a__z
mark = a__z

(17) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

Could not prove a rewrite lemma for the defined symbol a__z.

(18) Obligation:

TRS:
Rules:
a__aa__c
a__ba__c
a__ce
a__kl
a__dm
a__aa__d
a__ba__d
a__cl
a__km
a__Aa__h(a__f(a__a), a__f(a__b))
a__h(X, X) → a__g(mark(X), mark(X), a__f(a__k))
a__g(d, X, X) → a__A
a__f(X) → a__z(mark(X), X)
a__z(e, X) → mark(X)
mark(A) → a__A
mark(a) → a__a
mark(b) → a__b
mark(c) → a__c
mark(d) → a__d
mark(k) → a__k
mark(z(X1, X2)) → a__z(mark(X1), X2)
mark(f(X)) → a__f(mark(X))
mark(h(X1, X2)) → a__h(mark(X1), mark(X2))
mark(g(X1, X2, X3)) → a__g(mark(X1), mark(X2), mark(X3))
mark(e) → e
mark(l) → l
mark(m) → m
a__AA
a__aa
a__bb
a__cc
a__dd
a__kk
a__z(X1, X2) → z(X1, X2)
a__f(X) → f(X)
a__h(X1, X2) → h(X1, X2)
a__g(X1, X2, X3) → g(X1, X2, X3)

Types:
a__a :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__c :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__b :: e:l:m:d:A:a:b:c:k:z:f:h:g
e :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__k :: e:l:m:d:A:a:b:c:k:z:f:h:g
l :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__d :: e:l:m:d:A:a:b:c:k:z:f:h:g
m :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
mark :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
d :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a :: e:l:m:d:A:a:b:c:k:z:f:h:g
b :: e:l:m:d:A:a:b:c:k:z:f:h:g
c :: e:l:m:d:A:a:b:c:k:z:f:h:g
k :: e:l:m:d:A:a:b:c:k:z:f:h:g
z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
hole_e:l:m:d:A:a:b:c:k:z:f:h:g1_0 :: e:l:m:d:A:a:b:c:k:z:f:h:g
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0 :: Nat → e:l:m:d:A:a:b:c:k:z:f:h:g

Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)

The following defined symbols remain to be analysed:
mark

They will be analysed ascendingly in the following order:
a__A = a__h
a__A = a__f
a__A = a__g
a__A = mark
a__A = a__z
a__h = a__f
a__h = a__g
a__h = mark
a__h = a__z
a__f = a__g
a__f = mark
a__f = a__z
a__g = mark
a__g = a__z
mark = a__z

(19) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(n11571540_0)) → gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0), rt ∈ Ω(1 + n115715400)

Induction Base:
mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0)) →RΩ(1)
e

Induction Step:
mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(n11571540_0, 1))) →RΩ(1)
a__z(mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(n11571540_0)), e) →IH
a__z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0), e) →RΩ(1)
mark(e) →RΩ(1)
e

We have rt ∈ Ω(n1) and sz ∈ O(n). Thus, we have ircR ∈ Ω(n).

(20) Complex Obligation (BEST)

(21) Obligation:

TRS:
Rules:
a__aa__c
a__ba__c
a__ce
a__kl
a__dm
a__aa__d
a__ba__d
a__cl
a__km
a__Aa__h(a__f(a__a), a__f(a__b))
a__h(X, X) → a__g(mark(X), mark(X), a__f(a__k))
a__g(d, X, X) → a__A
a__f(X) → a__z(mark(X), X)
a__z(e, X) → mark(X)
mark(A) → a__A
mark(a) → a__a
mark(b) → a__b
mark(c) → a__c
mark(d) → a__d
mark(k) → a__k
mark(z(X1, X2)) → a__z(mark(X1), X2)
mark(f(X)) → a__f(mark(X))
mark(h(X1, X2)) → a__h(mark(X1), mark(X2))
mark(g(X1, X2, X3)) → a__g(mark(X1), mark(X2), mark(X3))
mark(e) → e
mark(l) → l
mark(m) → m
a__AA
a__aa
a__bb
a__cc
a__dd
a__kk
a__z(X1, X2) → z(X1, X2)
a__f(X) → f(X)
a__h(X1, X2) → h(X1, X2)
a__g(X1, X2, X3) → g(X1, X2, X3)

Types:
a__a :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__c :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__b :: e:l:m:d:A:a:b:c:k:z:f:h:g
e :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__k :: e:l:m:d:A:a:b:c:k:z:f:h:g
l :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__d :: e:l:m:d:A:a:b:c:k:z:f:h:g
m :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
mark :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
d :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a :: e:l:m:d:A:a:b:c:k:z:f:h:g
b :: e:l:m:d:A:a:b:c:k:z:f:h:g
c :: e:l:m:d:A:a:b:c:k:z:f:h:g
k :: e:l:m:d:A:a:b:c:k:z:f:h:g
z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
hole_e:l:m:d:A:a:b:c:k:z:f:h:g1_0 :: e:l:m:d:A:a:b:c:k:z:f:h:g
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0 :: Nat → e:l:m:d:A:a:b:c:k:z:f:h:g

Lemmas:
mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(n11571540_0)) → gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0), rt ∈ Ω(1 + n115715400)

Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)

The following defined symbols remain to be analysed:
a__h, a__A, a__f, a__g, a__z

They will be analysed ascendingly in the following order:
a__A = a__h
a__A = a__f
a__A = a__g
a__A = mark
a__A = a__z
a__h = a__f
a__h = a__g
a__h = mark
a__h = a__z
a__f = a__g
a__f = mark
a__f = a__z
a__g = mark
a__g = a__z
mark = a__z

(22) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

Could not prove a rewrite lemma for the defined symbol a__h.

(23) Obligation:

TRS:
Rules:
a__aa__c
a__ba__c
a__ce
a__kl
a__dm
a__aa__d
a__ba__d
a__cl
a__km
a__Aa__h(a__f(a__a), a__f(a__b))
a__h(X, X) → a__g(mark(X), mark(X), a__f(a__k))
a__g(d, X, X) → a__A
a__f(X) → a__z(mark(X), X)
a__z(e, X) → mark(X)
mark(A) → a__A
mark(a) → a__a
mark(b) → a__b
mark(c) → a__c
mark(d) → a__d
mark(k) → a__k
mark(z(X1, X2)) → a__z(mark(X1), X2)
mark(f(X)) → a__f(mark(X))
mark(h(X1, X2)) → a__h(mark(X1), mark(X2))
mark(g(X1, X2, X3)) → a__g(mark(X1), mark(X2), mark(X3))
mark(e) → e
mark(l) → l
mark(m) → m
a__AA
a__aa
a__bb
a__cc
a__dd
a__kk
a__z(X1, X2) → z(X1, X2)
a__f(X) → f(X)
a__h(X1, X2) → h(X1, X2)
a__g(X1, X2, X3) → g(X1, X2, X3)

Types:
a__a :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__c :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__b :: e:l:m:d:A:a:b:c:k:z:f:h:g
e :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__k :: e:l:m:d:A:a:b:c:k:z:f:h:g
l :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__d :: e:l:m:d:A:a:b:c:k:z:f:h:g
m :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
mark :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
d :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a :: e:l:m:d:A:a:b:c:k:z:f:h:g
b :: e:l:m:d:A:a:b:c:k:z:f:h:g
c :: e:l:m:d:A:a:b:c:k:z:f:h:g
k :: e:l:m:d:A:a:b:c:k:z:f:h:g
z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
hole_e:l:m:d:A:a:b:c:k:z:f:h:g1_0 :: e:l:m:d:A:a:b:c:k:z:f:h:g
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0 :: Nat → e:l:m:d:A:a:b:c:k:z:f:h:g

Lemmas:
mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(n11571540_0)) → gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0), rt ∈ Ω(1 + n115715400)

Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)

The following defined symbols remain to be analysed:
a__g, a__A, a__f, a__z

They will be analysed ascendingly in the following order:
a__A = a__h
a__A = a__f
a__A = a__g
a__A = mark
a__A = a__z
a__h = a__f
a__h = a__g
a__h = mark
a__h = a__z
a__f = a__g
a__f = mark
a__f = a__z
a__g = mark
a__g = a__z
mark = a__z

(24) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

Could not prove a rewrite lemma for the defined symbol a__g.

(25) Obligation:

TRS:
Rules:
a__aa__c
a__ba__c
a__ce
a__kl
a__dm
a__aa__d
a__ba__d
a__cl
a__km
a__Aa__h(a__f(a__a), a__f(a__b))
a__h(X, X) → a__g(mark(X), mark(X), a__f(a__k))
a__g(d, X, X) → a__A
a__f(X) → a__z(mark(X), X)
a__z(e, X) → mark(X)
mark(A) → a__A
mark(a) → a__a
mark(b) → a__b
mark(c) → a__c
mark(d) → a__d
mark(k) → a__k
mark(z(X1, X2)) → a__z(mark(X1), X2)
mark(f(X)) → a__f(mark(X))
mark(h(X1, X2)) → a__h(mark(X1), mark(X2))
mark(g(X1, X2, X3)) → a__g(mark(X1), mark(X2), mark(X3))
mark(e) → e
mark(l) → l
mark(m) → m
a__AA
a__aa
a__bb
a__cc
a__dd
a__kk
a__z(X1, X2) → z(X1, X2)
a__f(X) → f(X)
a__h(X1, X2) → h(X1, X2)
a__g(X1, X2, X3) → g(X1, X2, X3)

Types:
a__a :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__c :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__b :: e:l:m:d:A:a:b:c:k:z:f:h:g
e :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__k :: e:l:m:d:A:a:b:c:k:z:f:h:g
l :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__d :: e:l:m:d:A:a:b:c:k:z:f:h:g
m :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
mark :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
d :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a :: e:l:m:d:A:a:b:c:k:z:f:h:g
b :: e:l:m:d:A:a:b:c:k:z:f:h:g
c :: e:l:m:d:A:a:b:c:k:z:f:h:g
k :: e:l:m:d:A:a:b:c:k:z:f:h:g
z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
hole_e:l:m:d:A:a:b:c:k:z:f:h:g1_0 :: e:l:m:d:A:a:b:c:k:z:f:h:g
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0 :: Nat → e:l:m:d:A:a:b:c:k:z:f:h:g

Lemmas:
mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(n11571540_0)) → gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0), rt ∈ Ω(1 + n115715400)

Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)

The following defined symbols remain to be analysed:
a__A, a__f, a__z

They will be analysed ascendingly in the following order:
a__A = a__h
a__A = a__f
a__A = a__g
a__A = mark
a__A = a__z
a__h = a__f
a__h = a__g
a__h = mark
a__h = a__z
a__f = a__g
a__f = mark
a__f = a__z
a__g = mark
a__g = a__z
mark = a__z

(26) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

Could not prove a rewrite lemma for the defined symbol a__A.

(27) Obligation:

TRS:
Rules:
a__aa__c
a__ba__c
a__ce
a__kl
a__dm
a__aa__d
a__ba__d
a__cl
a__km
a__Aa__h(a__f(a__a), a__f(a__b))
a__h(X, X) → a__g(mark(X), mark(X), a__f(a__k))
a__g(d, X, X) → a__A
a__f(X) → a__z(mark(X), X)
a__z(e, X) → mark(X)
mark(A) → a__A
mark(a) → a__a
mark(b) → a__b
mark(c) → a__c
mark(d) → a__d
mark(k) → a__k
mark(z(X1, X2)) → a__z(mark(X1), X2)
mark(f(X)) → a__f(mark(X))
mark(h(X1, X2)) → a__h(mark(X1), mark(X2))
mark(g(X1, X2, X3)) → a__g(mark(X1), mark(X2), mark(X3))
mark(e) → e
mark(l) → l
mark(m) → m
a__AA
a__aa
a__bb
a__cc
a__dd
a__kk
a__z(X1, X2) → z(X1, X2)
a__f(X) → f(X)
a__h(X1, X2) → h(X1, X2)
a__g(X1, X2, X3) → g(X1, X2, X3)

Types:
a__a :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__c :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__b :: e:l:m:d:A:a:b:c:k:z:f:h:g
e :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__k :: e:l:m:d:A:a:b:c:k:z:f:h:g
l :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__d :: e:l:m:d:A:a:b:c:k:z:f:h:g
m :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
mark :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
d :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a :: e:l:m:d:A:a:b:c:k:z:f:h:g
b :: e:l:m:d:A:a:b:c:k:z:f:h:g
c :: e:l:m:d:A:a:b:c:k:z:f:h:g
k :: e:l:m:d:A:a:b:c:k:z:f:h:g
z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
hole_e:l:m:d:A:a:b:c:k:z:f:h:g1_0 :: e:l:m:d:A:a:b:c:k:z:f:h:g
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0 :: Nat → e:l:m:d:A:a:b:c:k:z:f:h:g

Lemmas:
mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(n11571540_0)) → gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0), rt ∈ Ω(1 + n115715400)

Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)

The following defined symbols remain to be analysed:
a__f, a__z

They will be analysed ascendingly in the following order:
a__A = a__h
a__A = a__f
a__A = a__g
a__A = mark
a__A = a__z
a__h = a__f
a__h = a__g
a__h = mark
a__h = a__z
a__f = a__g
a__f = mark
a__f = a__z
a__g = mark
a__g = a__z
mark = a__z

(28) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

Could not prove a rewrite lemma for the defined symbol a__f.

(29) Obligation:

TRS:
Rules:
a__aa__c
a__ba__c
a__ce
a__kl
a__dm
a__aa__d
a__ba__d
a__cl
a__km
a__Aa__h(a__f(a__a), a__f(a__b))
a__h(X, X) → a__g(mark(X), mark(X), a__f(a__k))
a__g(d, X, X) → a__A
a__f(X) → a__z(mark(X), X)
a__z(e, X) → mark(X)
mark(A) → a__A
mark(a) → a__a
mark(b) → a__b
mark(c) → a__c
mark(d) → a__d
mark(k) → a__k
mark(z(X1, X2)) → a__z(mark(X1), X2)
mark(f(X)) → a__f(mark(X))
mark(h(X1, X2)) → a__h(mark(X1), mark(X2))
mark(g(X1, X2, X3)) → a__g(mark(X1), mark(X2), mark(X3))
mark(e) → e
mark(l) → l
mark(m) → m
a__AA
a__aa
a__bb
a__cc
a__dd
a__kk
a__z(X1, X2) → z(X1, X2)
a__f(X) → f(X)
a__h(X1, X2) → h(X1, X2)
a__g(X1, X2, X3) → g(X1, X2, X3)

Types:
a__a :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__c :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__b :: e:l:m:d:A:a:b:c:k:z:f:h:g
e :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__k :: e:l:m:d:A:a:b:c:k:z:f:h:g
l :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__d :: e:l:m:d:A:a:b:c:k:z:f:h:g
m :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
mark :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
d :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a :: e:l:m:d:A:a:b:c:k:z:f:h:g
b :: e:l:m:d:A:a:b:c:k:z:f:h:g
c :: e:l:m:d:A:a:b:c:k:z:f:h:g
k :: e:l:m:d:A:a:b:c:k:z:f:h:g
z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
hole_e:l:m:d:A:a:b:c:k:z:f:h:g1_0 :: e:l:m:d:A:a:b:c:k:z:f:h:g
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0 :: Nat → e:l:m:d:A:a:b:c:k:z:f:h:g

Lemmas:
mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(n11571540_0)) → gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0), rt ∈ Ω(1 + n115715400)

Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)

The following defined symbols remain to be analysed:
a__z

They will be analysed ascendingly in the following order:
a__A = a__h
a__A = a__f
a__A = a__g
a__A = mark
a__A = a__z
a__h = a__f
a__h = a__g
a__h = mark
a__h = a__z
a__f = a__g
a__f = mark
a__f = a__z
a__g = mark
a__g = a__z
mark = a__z

(30) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

Could not prove a rewrite lemma for the defined symbol a__z.

(31) Obligation:

TRS:
Rules:
a__aa__c
a__ba__c
a__ce
a__kl
a__dm
a__aa__d
a__ba__d
a__cl
a__km
a__Aa__h(a__f(a__a), a__f(a__b))
a__h(X, X) → a__g(mark(X), mark(X), a__f(a__k))
a__g(d, X, X) → a__A
a__f(X) → a__z(mark(X), X)
a__z(e, X) → mark(X)
mark(A) → a__A
mark(a) → a__a
mark(b) → a__b
mark(c) → a__c
mark(d) → a__d
mark(k) → a__k
mark(z(X1, X2)) → a__z(mark(X1), X2)
mark(f(X)) → a__f(mark(X))
mark(h(X1, X2)) → a__h(mark(X1), mark(X2))
mark(g(X1, X2, X3)) → a__g(mark(X1), mark(X2), mark(X3))
mark(e) → e
mark(l) → l
mark(m) → m
a__AA
a__aa
a__bb
a__cc
a__dd
a__kk
a__z(X1, X2) → z(X1, X2)
a__f(X) → f(X)
a__h(X1, X2) → h(X1, X2)
a__g(X1, X2, X3) → g(X1, X2, X3)

Types:
a__a :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__c :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__b :: e:l:m:d:A:a:b:c:k:z:f:h:g
e :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__k :: e:l:m:d:A:a:b:c:k:z:f:h:g
l :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__d :: e:l:m:d:A:a:b:c:k:z:f:h:g
m :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
mark :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
d :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a :: e:l:m:d:A:a:b:c:k:z:f:h:g
b :: e:l:m:d:A:a:b:c:k:z:f:h:g
c :: e:l:m:d:A:a:b:c:k:z:f:h:g
k :: e:l:m:d:A:a:b:c:k:z:f:h:g
z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
hole_e:l:m:d:A:a:b:c:k:z:f:h:g1_0 :: e:l:m:d:A:a:b:c:k:z:f:h:g
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0 :: Nat → e:l:m:d:A:a:b:c:k:z:f:h:g

Lemmas:
mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(n11571540_0)) → gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0), rt ∈ Ω(1 + n115715400)

Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)

No more defined symbols left to analyse.

(32) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n1) was proven with the following lemma:
mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(n11571540_0)) → gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0), rt ∈ Ω(1 + n115715400)

(33) BOUNDS(n^1, INF)

(34) Obligation:

TRS:
Rules:
a__aa__c
a__ba__c
a__ce
a__kl
a__dm
a__aa__d
a__ba__d
a__cl
a__km
a__Aa__h(a__f(a__a), a__f(a__b))
a__h(X, X) → a__g(mark(X), mark(X), a__f(a__k))
a__g(d, X, X) → a__A
a__f(X) → a__z(mark(X), X)
a__z(e, X) → mark(X)
mark(A) → a__A
mark(a) → a__a
mark(b) → a__b
mark(c) → a__c
mark(d) → a__d
mark(k) → a__k
mark(z(X1, X2)) → a__z(mark(X1), X2)
mark(f(X)) → a__f(mark(X))
mark(h(X1, X2)) → a__h(mark(X1), mark(X2))
mark(g(X1, X2, X3)) → a__g(mark(X1), mark(X2), mark(X3))
mark(e) → e
mark(l) → l
mark(m) → m
a__AA
a__aa
a__bb
a__cc
a__dd
a__kk
a__z(X1, X2) → z(X1, X2)
a__f(X) → f(X)
a__h(X1, X2) → h(X1, X2)
a__g(X1, X2, X3) → g(X1, X2, X3)

Types:
a__a :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__c :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__b :: e:l:m:d:A:a:b:c:k:z:f:h:g
e :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__k :: e:l:m:d:A:a:b:c:k:z:f:h:g
l :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__d :: e:l:m:d:A:a:b:c:k:z:f:h:g
m :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
a__g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
mark :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
d :: e:l:m:d:A:a:b:c:k:z:f:h:g
a__z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
A :: e:l:m:d:A:a:b:c:k:z:f:h:g
a :: e:l:m:d:A:a:b:c:k:z:f:h:g
b :: e:l:m:d:A:a:b:c:k:z:f:h:g
c :: e:l:m:d:A:a:b:c:k:z:f:h:g
k :: e:l:m:d:A:a:b:c:k:z:f:h:g
z :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
f :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
h :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
g :: e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g → e:l:m:d:A:a:b:c:k:z:f:h:g
hole_e:l:m:d:A:a:b:c:k:z:f:h:g1_0 :: e:l:m:d:A:a:b:c:k:z:f:h:g
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0 :: Nat → e:l:m:d:A:a:b:c:k:z:f:h:g

Lemmas:
mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(n11571540_0)) → gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0), rt ∈ Ω(1 + n115715400)

Generator Equations:
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0) ⇔ e
gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(+(x, 1)) ⇔ z(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(x), e)

No more defined symbols left to analyse.

(35) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n1) was proven with the following lemma:
mark(gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(n11571540_0)) → gen_e:l:m:d:A:a:b:c:k:z:f:h:g2_0(0), rt ∈ Ω(1 + n115715400)

(36) BOUNDS(n^1, INF)